import java.util.*;

public class Solution {
    static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

        private TreeNode cur = null;    //遍历的当前节点
        private TreeNode head = null;    //生成链表的头节点

        public TreeNode Convert(TreeNode pRootOfTree) {
            if (pRootOfTree == null) {
                return null;
            }
            TreeNode root = pRootOfTree;
            TreeNode cur = pRootOfTree;//中序遍历二叉树
            TreeNode par = null;//cur的前一个节点
            Stack<TreeNode> stack = new Stack<>();
            //找到链表的头节点
            while (cur != null) {
                cur = cur.left;
            }
            pRootOfTree = cur;
            cur = root;
            //非递归中序遍历
            while (cur != null || !stack.isEmpty()) {
                //把cur的左树放入stack
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                cur = stack.pop();
                if (cur == pRootOfTree) {
                    par = cur;
                } else {
                    //转化节点
                    cur.left = par;
                    par.right = cur;
                    par = cur;
                }
                cur = cur.right;
            }
            return pRootOfTree;
        }
    }
}
